#include <bits/stdc++.h>
// 2025/02/07
// tag:
// Author: Zhang Muen
using namespace std;
class State {
public:
    int64_t id, weight;
    State(int i, int w)
    {
        id = i;
        weight = w;
    }
};

struct cmp {
    bool operator()(State& a, State& b)
    {
        return a.weight > b.weight;
    }
};

int64_t n, m, s, dist[1000001], cnt[1000001];
vector<State> graph[1000001];
bitset<1000001> vis;

void Dijkstra(int64_t start)
{
    for (int i = 1; i <= n; i++)
        dist[i] = INT64_MAX;
    cnt[start] = 1, dist[start] = 0;
    priority_queue<State, vector<State>, cmp> pq;
    pq.push(State(start, 0));
    while (!pq.empty()) {
        State state = pq.top();
        pq.pop();
        int Dist = state.weight;
        if (vis[state.id])
            continue;
        vis[state.id] = true;
        for (auto neighbor : graph[state.id]) {
            int Dist2 = Dist + neighbor.weight;
            if (dist[neighbor.id] > Dist2) {
                dist[neighbor.id] = Dist2;
                cnt[neighbor.id] = cnt[state.id];
                pq.push(State(neighbor.id, Dist2));
            }
            else if (dist[neighbor.id] == Dist2)
                cnt[neighbor.id] += cnt[state.id], cnt[neighbor.id] %= 100003;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int64_t u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        graph[u].push_back(State(v, 1));
        graph[v].push_back(State(u, 1));
    }
    Dijkstra(1);
    for (int i = 1; i <= n; i++)
        cout << cnt[i] << endl;
    return 0;
}